﻿using System;

namespace h129
{
    public class Solution
    {
        public int Rob(int[] nums)
        {
            if (nums == null || nums.Length <= 0) return 0;
            /**
            
            抢第一天，就不能抢最后一天
            抢最后一天 ，就不能抢第一天
    
            所以我们可分为两段
    
            0-N-1
            1-N
            比较这两段的最大值
    
            注意边界条件，如果只有一间房子，直接返回first
            少于2间房，返回first,second的最大值 
    
            如果我不偷第一间，我就得偷第2、3间，那么我必须至少有三间房才可以
    
            */

            int first = nums[0];
            if (nums.Length == 1) return first;
            int second = Math.Max(nums[0], nums[1]);
            int max = Math.Max(first, second);

            if (nums.Length < 3) return max;

            for (int i = 2; i < nums.Length - 1; ++i)
            {
                max = Math.Max(first + nums[i], second);
                first = second;
                second = max;
            }

            var tmp = max;

            first = nums[1];
            second = Math.Max(nums[1], nums[2]);
            max = Math.Max(first, second);
            for (int i = 3; i < nums.Length; ++i)
            {
                max = Math.Max(first + nums[i], second);
                first = second;
                second = max;
            }

            return Math.Max(max, tmp);
        }
    }
}